//
// Created by DengLibin on 2019/1/25 0025.
//

#include <iostream>
#include <vector>
using namespace std;

/**
 * 买股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。
 * @return
 */
int max_(int x, int y){
    return x > y ? x : y;
}
int maxProfit(vector<int>& prices) {
    int len = prices.size();
    if(len < 2){
        return 0;
    }
    int min_index = 0; //股票价格最低的那一天
    int max_index = 0; //股票价格最高那一天 （max_index >= min_index）
    int max = 0;
    for(int i = 0; i < len; i++){
        if(prices[i]<=prices[min_index]){ //找到价格最低的那一天
            min_index = i;
            max_index = i;
        }
        if(prices[i]>= prices[max_index]){ //找到股票价格更高的一天
            max_index=i;
        }
        max = max_(max, prices[max_index]-prices[min_index]); //求最大值
    }
    return max;
}
int main78(){

    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);
    cout << maxProfit(v);
    return 0;
}